package com.bing.java.sort;

import java.util.Arrays;

/**
 * 归并排序
 * 
 * 时间复杂度：O(nlog2n)
 * @author bing
 *
 *         2019年11月11日 下午2:20:56
 * 
 *         对于给定的一组记录，利用递归与分治技术将数据序列划分成为越来越小的半子表(直到剩余一个数字)，在对半子表排序，
 *         最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。 (1)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 *         (2)设定两个指针，最初位置分别为两个已经排序序列的起始位置
 *         (3)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 (4)重复步骤3直到某一指针达到序列尾
 *         (5)将另一序列剩下的所有元素直接复制到合并序列尾
 */
public class SortMerge {

	public static void main(String[] args) {
		int[] a = { 5, 3, 12, 8, 7 };
		mergeSort(a, 0, a.length - 1);
		System.out.println("排序后的数组：" + Arrays.toString(a));
	}

	// 归并排序
	public static int[] mergeSort(int[] array, int low, int high) {
		if (low < high) {
			int mid = (low + high) / 2;
			mergeSort(array, low, mid);
			mergeSort(array, mid + 1, high);
			merge(array, low, mid, high);// 归并
		}
		return array;
	}

	private static void merge(int[] array, int low, int mid, int high) {
		int i = low;// 指针，前一个序列的头指针
		int j = mid + 1;// 指针，后一个序列的头指针
		int[] temp = new int[high - low + 1];
		int k = 0;
		while (i <= mid && j <= high) {
			if (array[i] < array[j]) {// 从头比较两个序列，小的放入临时数组temp
				temp[k++] = array[i++];// 前一个序列指针后移一位
			} else {
				temp[k++] = array[j++];// 后一个序列指针后移一位
			}

		}
		// 最后只会剩下一组序列
		while (i <= mid) {
			temp[k++] = array[i++];// 把前一个指针剩余的数字放入临时数组
		}
		while (j <= high) {
			temp[k++] = array[j++];// 把后一个指针剩余的数字放入临时数组
		}

		for (int m = 0; m < high - low + 1; m++) {
			array[low + m] = temp[m];
		}
	}
}
